package leetcode;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

/**
 * ClassName: HengshengT1
 * Package: leetcode
 * Description:
 *
 * @Author wjn
 * @Create 2025/10/10 19:50
 * @Version 1.0
 */
public class HengshengT2 {

    private static final int MAX_VAL = 1000001;
    private static int[] states = new int[MAX_VAL];

    public static void preprocess() {

        for (int i = 0; i < MAX_VAL; i++) {
            states[i] = i;
        }
        for (int i = 2; i * i < MAX_VAL; i++) {
            long square = (long) i * i;
            for (int j = (int) square; j < MAX_VAL; j += square) {
                while (states[j] % square == 0) {
                    states[j] /= square;
                }
            }
        }
    }

    private static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) throws IOException {
        preprocess();

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String nStr = reader.readLine();

        if (nStr == null || nStr.trim().isEmpty()) {
            System.out.println(-1);
            return;
        }
        int n = Integer.parseInt(nStr);

        if (n == 0) {
            System.out.println(-1);
            return;
        }

        int[] a = new int[n];
        StringTokenizer st = new StringTokenizer(reader.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        Map<Long, Integer> firstOccurrences = new HashMap<>();
        int maxLength = 0;
        long currentPrefixState = 1L;

        firstOccurrences.put(1L, -1);

        for (int i = 0; i < n; i++) {

            long elementState = states[a[i]];
            long commonFactor = gcd(currentPrefixState, elementState);
            currentPrefixState = (currentPrefixState * elementState) / (commonFactor * commonFactor);

            if (firstOccurrences.containsKey(currentPrefixState)) {
                int length = i - firstOccurrences.get(currentPrefixState);
                if (length > maxLength) {
                    maxLength = length;
                }

            } else {
                firstOccurrences.put(currentPrefixState, i);
            }

        }
        if (maxLength > 0) {
            System.out.println(maxLength);
        } else {
            System.out.println(-1);
        }
    }
}
